home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 015 / bawk2a.arc / BAWKPAT.C < prev    next >
Encoding:
C/C++ Source or Header  |  1986-07-27  |  9.0 KB  |  340 lines
  1. /*
  2.  * Bawk regular expression compiler/interpreter
  3.  */
  4. #include <stdio.h>
  5. #include "bawk.h"
  6.  
  7. re_compile( patbuf )
  8. char *patbuf; /* where to put compiled pattern */
  9. {     
  10. /*
  11.  * Compile a regular expression from current input file
  12.  * into the given pattern buffer.
  13.  */
  14.     int c,                   /* Current character         */
  15.     o;                       /* Temp                      */
  16.     char *patptr,            /* destination string pntr   */
  17.     *lp,                     /* Last pattern pointer      */
  18.     *spp,                    /* Save beginning of pattern */
  19.     delim,                   /* pattern delimiter         */
  20.     *cclass();               /* Compile class routine     */
  21.  
  22.     patptr = patbuf;
  23.     delim = getcharacter();
  24.  
  25.     while ( (c = getcharacter()) != -1 && c != delim ) { 
  26. /*
  27.  * STAR, PLUS and MINUS are special.
  28.  */
  29.         if (c == '*' || c == '+' || c == '-') {
  30.             if (patptr == patbuf ||
  31.                 (o=patptr[-1]) == BOL ||
  32.                 o == EOL ||
  33.                 o == STAR ||
  34.                 o == PLUS ||
  35.                 o == MINUS)
  36.                 error( "illegal occurrance op", RE_ERROR );
  37.             *patptr++ = ENDPAT;
  38.             *patptr++ = ENDPAT;
  39.             spp = patptr;               /* Save pattern end     */
  40.             while (--patptr > lp)       /* Move pattern down... */
  41.                 *patptr = patptr[-1];    /* one byte     */
  42.             *patptr = (c == '*') ? STAR : (c == '-') ? MINUS : PLUS;
  43.             patptr = spp; /* Restore pattern end  */
  44.             continue;
  45.             }
  46. /*
  47.  * All the rest.
  48.  */
  49.         lp = patptr; /* Remember start       */
  50.         switch(c) {
  51.            case '^':
  52.                *patptr++ = BOL;
  53.                break;
  54.            case '$':
  55.                *patptr++ = EOL;
  56.                break;
  57.            case '.':
  58.                *patptr++ = ANY;
  59.                break;
  60.            case '[':
  61.                patptr = cclass( patptr );
  62.                break;
  63.            case ':':
  64.                if ( (c=getcharacter()) != -1 ) { 
  65.                    switch( tolower( c ) ) { 
  66.                       case 'a':
  67.                           *patptr++ = ALPHA;
  68.                           break;
  69.                       case 'd':
  70.                           *patptr++ = DIGIT;
  71.                           break;
  72.                       case 'n':
  73.                           *patptr++ = NALPHA;
  74.                           break;
  75.                       case ' ':
  76.                           *patptr++ = PUNCT;
  77.                           break;
  78.                       default:
  79.                           error( "unknown ':' type", RE_ERROR );
  80.                        }
  81.                    }
  82.                else error( "no ':' type", RE_ERROR );
  83.                break;
  84.            case '\\':
  85.                c = getcharacter();
  86.            default:
  87.                *patptr++ = CHAR;
  88.                *patptr++ = c;
  89.            }
  90.         }
  91.     *patptr++ = ENDPAT;
  92.     *patptr++ = 0;                  /* Terminate string     */
  93.  
  94. #ifdef DEBUG
  95.     if ( Debug>1 ) { 
  96.         for ( lp=patbuf; lp<patptr; ++lp ) { 
  97.             switch ( c = *lp ) { 
  98.                case CHAR:
  99.                    printf("char "); 
  100.                    break;
  101.                case BOL:
  102.                    printf("bol "); 
  103.                    break;
  104.                case EOL:
  105.                    printf("eol "); 
  106.                    break;
  107.                case ANY:
  108.                    printf("any "); 
  109.                    break;
  110.                case CLASS:
  111.                    printf("class(%d) ", *++lp); 
  112.                    break;
  113.                case NCLASS:
  114.                    printf("notclass(%d) ",*++lp); 
  115.                    break;
  116.                case STAR:
  117.                    printf("star "); 
  118.                    break;
  119.                case PLUS:
  120.                    printf("plus "); 
  121.                    break;
  122.                case MINUS:
  123.                    printf("minus "); 
  124.                    break;
  125.                case ALPHA:
  126.                    printf("alpha "); 
  127.                    break;
  128.                case DIGIT:
  129.                    printf("digit "); 
  130.                    break;
  131.                case NALPHA:
  132.                    printf("notalpha "); 
  133.                    break;
  134.                case PUNCT:
  135.                    printf("punct "); 
  136.                    break;
  137.                case RANGE:
  138.                    printf("range "); 
  139.                    break;
  140.                case ENDPAT:
  141.                    printf("endpat "); 
  142.                    break;
  143.                default:
  144.                    printf("<%c> ", c); 
  145.                    break;
  146.                 }
  147.             }
  148.         printf( "\n" );
  149.         }
  150. #endif
  151.  
  152.     return patptr - patbuf;
  153.     }
  154.  
  155. char *
  156. cclass( patbuf )
  157. char *patbuf; /* destination pattern buffer */
  158. {     
  159. /*
  160.  * Compile a class (within [])
  161.  */
  162.     char *patptr,        /* destination pattern pointer */
  163.     *cp;                 /* Pattern start     */
  164.     int c,               /* Current character */
  165.     o;                   /* Temp              */
  166.  
  167.     patptr = patbuf;
  168.  
  169.     if ( (c = getcharacter()) == -1 )
  170.         error( "class terminates badly", RE_ERROR );
  171.     else if ( c == '^') { 
  172. /*
  173.  * Class exclusion, for example: [^abc]
  174.  * Swallow the "^" and set token type to class exclusion.
  175.  */
  176.         o = NCLASS;
  177.         }
  178.     else { 
  179. /*
  180.  * Normal class, for example: [abc]
  181.  * push back the character and set token type to class
  182.  */
  183.         ungetcharacter( c );
  184.         o = CLASS;
  185.         }
  186.     *patptr++ = o;
  187.  
  188.     cp = patptr;                       /* remember where byte count is */
  189.     *patptr++ = 0;                     /* and initialize byte count */
  190.     while ( (c = getcharacter()) != -1 && c!=']' ) { 
  191.         o = getcharacter();             /* peek at next char */
  192.         if (c == '\\') {                /* Store quoted chars */
  193.             if ( o == -1)                /* Gotta get something */
  194.                 error( "class terminates badly", RE_ERROR );
  195.             *patptr++ = o;
  196.             }
  197.         else if ( c=='-' && (patptr-cp)>1 && o!=']' && o != -1 ) { 
  198.             c = patptr[-1];              /* Range start     */
  199.             patptr[-1] = RANGE;          /* Range signal    */
  200.             *patptr++ = c;               /* Re-store start  */
  201.             *patptr++ = o;               /* Store end char  */
  202.             }
  203.         else { 
  204.             *patptr++ = c;               /* Store normal char */
  205.             ungetcharacter( o );
  206.             }
  207.         }
  208.     if (c != ']') error( "unterminated class", RE_ERROR );
  209.     if ( (c = (patptr - cp)) >= 256 ) error( "class too large", RE_ERROR );
  210.     if ( c == 0 ) error( "empty class", RE_ERROR );
  211.     *cp = c;                          /* fill in byte count */
  212.  
  213.     return patptr;
  214.     }
  215.  
  216. match( line, pattern )
  217. char *line; /* line to match */
  218. char *pattern; /* pattern to match */
  219. {     
  220. /*
  221.  * Match the current line (in Linebuf[]), return 1 if it does.
  222.  */
  223.     char *l;                       /* Line pointer       */
  224.     char *pmatch();
  225.     char *next;
  226.     int matches;
  227.  
  228.     matches = 0;
  229.     for (l = line; *l; l++) { 
  230.         if (( next = pmatch(line, l, pattern) ) != 0) { 
  231.             l = next - 1;
  232.             ++matches;
  233. #ifdef DEBUG
  234.             if ( Debug ) printf( "match!\n" );
  235. #endif
  236.             }
  237.         }
  238.     return matches;
  239.     }
  240.  
  241. char *
  242. pmatch(linestart, line, pattern)
  243. char *linestart;           /* start of line to match */
  244. char *line;                /* (partial) line to match      */
  245. char *pattern;             /* (partial) pattern to match   */
  246. {     
  247.     char *l;                /* Current line pointer         */
  248.     char *p;                /* Current pattern pointer      */
  249.     char c;                 /* Current character            */
  250.     char *e;                /* End for STAR and PLUS match  */
  251.     int op;                 /* Pattern operation            */
  252.     int n;                  /* Class counter                */
  253.     char *are;              /* Start of STAR match          */
  254.  
  255.     l = line;
  256.  
  257. #ifdef DEBUG
  258.     if (Debug > 1) printf("pmatch(\"%s\")\n", line);
  259. #endif
  260.  
  261.     p = pattern;
  262.     while ((op = *p++) != ENDPAT) {
  263.  
  264. #ifdef DEBUG
  265.         if (Debug > 1) printf("byte[%d] = 0%o, '%c', op = 0%o\n",
  266.         l-line, *l, *l, op);
  267. #endif
  268.  
  269.         switch(op) {
  270.            case CHAR:
  271.                if ( *l++ != *p++) return 0;
  272.                break;
  273.            case BOL:
  274.                if (l != linestart) return 0;
  275.                break;
  276.            case EOL:
  277.                if (*l != '\0') return 0;
  278.                break;
  279.            case ANY:
  280.                if (*l++ == '\0') return 0;
  281.                break;
  282.            case DIGIT:
  283.                if ((c = *l++) < '0' || (c > '9')) return 0;
  284.                break;
  285.            case ALPHA:
  286.                c = tolower( *l++ );
  287.                if (c < 'a' || c > 'z') return 0;
  288.                break;
  289.            case NALPHA:
  290.                c = tolower(*l++);
  291.                if (c >= 'a' && c <= 'z') break;
  292.                else if (c < '0' || c > '9') return 0;
  293.                break;
  294.            case PUNCT:
  295.                c = *l++;
  296.                if (c == 0 || c > ' ') return 0;
  297.                break;
  298.            case CLASS:
  299.            case NCLASS:
  300.                c = *l++;
  301.                n = *p++ & 0377;
  302.                do {     
  303.                    if (*p == RANGE) {
  304.                        p += 3;
  305.                        n -= 2;
  306.                        if (c >= p[-2] && c <= p[-1]) break;
  307.                        }
  308.                    else if (c == *p++) break;
  309.                    }
  310.                while (--n > 1);
  311.                if ((op == CLASS) == (n <= 1)) return 0;
  312.                if (op == CLASS) p += n - 2;
  313.                break;
  314.            case MINUS:
  315.                   e = pmatch(linestart,l,p);       /* Look for a match    */
  316.                while (*p++ != ENDPAT);             /* Skip over pattern   */
  317.                if (e)                              /* Got a match?        */
  318.                    l = e;                           /* Yes, update string  */
  319.                break;                              /* Always succeeds     */
  320.            case PLUS:                             /* One or more ...     */
  321.                if ((l = pmatch(linestart,l,p)) == 0)
  322.                    return 0;                        /* Gotta have a match  */
  323.            case STAR:                             /* Zero or more ...    */
  324.                are = l;                            /* Remember line start */
  325.                while (*l && ((e = pmatch(linestart,l,p)) != 0))
  326.                    l = e;                           /* Get longest match   */
  327.                while (*p++ != ENDPAT);             /* Skip over pattern   */
  328.                while (l >= are) {                  /* Try to match rest   */
  329.                    if ((e = pmatch(linestart,l,p)) != 0) return e;
  330.                    --l;                             /* Nope, try earlier   */
  331.                    }
  332.                return 0;                           /* Nothing else worked */
  333.            default:
  334.                fprintf( stderr, "bad op code %d\n", op );
  335.                error( "can't happen -- match", RE_ERROR );
  336.             }
  337.         }
  338.     return l;
  339.     }
  340.